package com.tgy.algorithm.base._贪心;


import java.util.Arrays;
import java.util.Comparator;

class ClassInfo{
    int start;
    int end;

    ClassInfo(int start, int end){
        this.start = start;
        this.end = end;
    }

    @Override
    public String toString() {

        return "(" + this.start + "," + this.end + ")";
    }
}

public class _排课_01 {

    public static int getMaxClassNum(ClassInfo[] classInfos) {

        return doGetMaxClassNum(classInfos,0,0);
    }

    public static int doGetMaxClassNum(ClassInfo[] classInfos,int classCount,int endTime) {

        if (classInfos.length == 0) {
            return classCount;
        }

        int length = classInfos.length;
        int maxCount =  classCount;
        for (int i = 0; i < length; i++) {
            ClassInfo classInfo = classInfos[i];
            if (classInfo.start >= endTime) {
                ClassInfo[] newClassInfos = copyClassInfos(classInfos, i);
                maxCount = Math.max(maxCount,doGetMaxClassNum(newClassInfos, classCount + 1, classInfo.end));
            }
        }

        return maxCount;
    }

    public static ClassInfo[] copyClassInfos(ClassInfo[] classInfos, int index) {
        ClassInfo[] newClassInfos = new ClassInfo[classInfos.length - 1];
        for (int i = 0; i < classInfos.length; i++) {
            if (i  < index) {
                newClassInfos[i] = classInfos[i];
            }else if (i > index) {
                newClassInfos[i - 1] = classInfos[i];
            }
        }

        return newClassInfos;
    }

    public static int getClassMaxNum(ClassInfo[] classInfos) {

        Arrays.sort(classInfos, new Comparator<ClassInfo>() {
            @Override
            public int compare(ClassInfo o1, ClassInfo o2) {
                return o1.end - o2.end;
            }
        });

        System.out.println(Arrays.toString(classInfos));

        int count = 0;
        int end = -1;
        for (int i = 0; i < classInfos.length; i++) {
            ClassInfo classInfo = classInfos[i];
            if (classInfo.start >= end) {
                count++;
                end = classInfo.end;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        ClassInfo[] classInfos = new ClassInfo[]{
                new ClassInfo(1, 10),
                new ClassInfo(9,11),
                new ClassInfo(10, 14)
        };
//        int maxClassNum = getMaxClassNum(classInfos);
//        System.out.println(maxClassNum);
        int classMaxNum = getClassMaxNum(classInfos);
        System.out.println(classMaxNum);
    }
}
